import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/3 9:37
 * @description 优先队列
 */
public class FreqStack {
    public static void main(String[] args) {
        FreqStack freqStack = new FreqStack();
        freqStack.push (5);//堆栈为 [5]
        freqStack.push (7);//堆栈是 [5,7]
        freqStack.push (5);//堆栈是 [5,7,5]
        freqStack.push (7);//堆栈是 [5,7,5,7]
        freqStack.push (4);//堆栈是 [5,7,5,7,4]
        freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
        freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
        freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
        freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
        freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。
    }

    /**
     * 最大堆，维护出现频率和位置 int[] {val, cnt, idx}
     */
    PriorityQueue<int[]> pq;
    Map<Integer, Integer> map;
    int idx;
    public FreqStack() {
        pq = new PriorityQueue<>((o1, o2) -> {
            // 频率相同，出现位置降序排序
            if (o1[1] == o2[1]) {
                return o2[2] - o1[2];
            }
            // 频率不同，频率降序排序
            return o2[1] - o1[1];
        });
        map = new HashMap<>();
        idx = 0;
    }

    public void push(int val) {
        map.put(val, map.getOrDefault(val, 0) + 1);
        pq.add(new int[]{val, map.get(val), ++idx});
    }

    public int pop() {
        int[] t = pq.poll();
        int val = t[0];
        if (map.get(val) == 1) {
            map.remove(val);
        }else {
            map.put(val, map.get(val) - 1);
        }
        return val;
    }
}
